package algorithm.leetcode.I1to100;

import algorithm.leetcode.ListNode;

public class Q24 {
    public ListNode swapPairs(ListNode head) {
        ListNode voidNode = new ListNode(-1);
        ListNode pre = voidNode;
        voidNode.next = head;

        // 终止条件
        while (pre.next != null && pre.next.next != null) {
            head = pre.next;
            ListNode next = head.next;
            ListNode post = next.next;

            pre = exchange(pre, head, next, post);
        }

        return voidNode.next;
    }

    public static ListNode exchange(ListNode pre, ListNode head, ListNode next, ListNode post) {
        pre.next = next;
        next.next = head;
        head.next = post;
        return head;
    }

    /**
     * 大佬用递归的方法实现
     * @param head
     * @return
     */
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        } else {
            ListNode next = head.next;
            head.next = swapPairs2(next.next);
            next.next = head;
            return next;
        }
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
//        ListNode f = new ListNode(6);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
//        e.next = f;
        Q24 tf = new Q24();
        System.out.println(tf.swapPairs2(a));

    }
}